The present invention relates to ray-box intersection testing, and more particularly to system and method for accelerating ray-box intersection testing in image rendering applications.
Given a ray in space, it is desirable to discover which (if any) object (e.g. a geometric primitive or a group of primitives) in a scene is first intersected by the ray. In some cases, these geometric primitives (e.g. points, lines, triangles, etc.) may be organized in a tree, such as a bounding volume hierarchy (BVH), k-dimensional (kd) tree, or a binary space partitioning (BSP) tree. After the geometric primitives are organized in such tree, ray tracing involves traversing the tree, searching for intersected nodes that contain primitives.
Regardless of the particular type of structure used for organizing the primitives, there are two basic operations that need to be executed during the tracing of a ray. The first operation is node traversal, i.e. finding the nodes that may contain primitives that the ray intersects. The second operation is primitive intersection, i.e. intersecting the ray against the primitives in a node found during node traversal. The execution of a ray tracing algorithm includes repeated application of these two operations in some order.
While the nodes of a tree can theoretically be of any shape, typically they are defined using axis-aligned planes or boxes. The virtues of axis-aligned acceleration structures are numerous: fast and robust construction, compact storage, and fast intersection tests.
FIG. 1 illustrates a conventional method for performing a ray-box intersection test as known in the art. At 102, the ray in question is intersected with two x-axis planes, at 104, the ray is intersected with y-axis planes, and at 106, the ray is intersected with two z-axis planes. At 108, the results of operations 102-106 are combined using minimum and maximum operations, particularly, an intersection (or span) is determined between a maximum value of the minimum x-, y- and z-plane endpoints and the a minimum value of the maximum x-, y- and z-plane endpoints. At 110, it is determined whether the span provided at 108 intersects the rays.
The following pseudocode describes a ray-box testing method using conventional instructions:                //O=ray origin (x, y, z)        //D=ray direction (x, y, z)        //B=axis-aligned box (xmin, ymin, zmin, xmax, ymax, zmax)        //tmin_ray=ray segment's minimum t value        //tmax_ray=ray segment's maximum t value        // RAY-BOX intersection (total 19 instructions)        // intersection with 6 axis-aligned planes (102, 104, 106), total 6 multiply-add instructionstx0=(B·xmin−O·x)/D·x; tx1=(B·xmax−O·x)/D·x; ty0=(B·ymin−O·y)/D·y; ty1=(B·ymax−O·y)/D·y; tz0=(B·zmin−O·z)/D·z; tz1=(B·zmax−O·z)/D·z;         // combine the results to [tmin,tmax] span (108), total 10 min/max instructionstmin=max(min(tx0,tx1),min(ty0,ty1),min(tz0,tz1));tmax=min(max(tx0,tx1),max(ty0,ty1),max(tz0,tz1));        // determine if the [tmin,tmax] overlaps with [tmin_ray,tmax_ray]        // (110), total 3 comparison instructionsbool intersect=(tmin<=tmax && tmax>=tmin_ray && tmin<=tmax_ray);        
Steps 102, 104 and 106 can be optimized, for example, by rewriting (B·xmin−O·x)/D·x as (B·xmin*1/D·x−O·x/D·x), where (1/D·x) and (O·x/D·x) can be precomputed so that the calculation can be implemented using a single multiply-add (MAD) instruction. This, however, is prone to numerical inaccuracies and comes at the expense of additional register usage because D and O are required in other stages of ray tracing. The inaccuracies create the possibility that the box's size is not correctly computed, and a ray which in fact intersects the box near the box's boundaries is not detected. Further, the ray-box intersection takes roughly 20 instructions on a typical instruction set which creates a significant bottleneck in the ray-tracing computation. Accordingly, what is needed is a system and method which can carry out the ray-box intersection test with increased accuracy and speed.